//============================================================================
// Name        : lab4_3.cpp
// Author      : 洪春晓
// Version     :
//Methods      : 贪心算法
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include "FileProcessor.cpp"
#include <iostream>
using namespace std;

#define IMPOSSIBLE "impossible"
#define INPUTFILENAME "input.txt"
#define OUTPUTFILENAME "output.txt"
#define COINTYPENUM 6

int value[COINTYPENUM] = {5,10,20,50,100,200};//硬币币种

int getChangeNum(int need);//得到店家找need的硬币数
int getGiveNum(int money,int *number);//得到顾客付出的硬币数
int main() {

	int question_num=0;//问题种数
	int *answer;//answer[i]表示问题i需要的最少硬币数
	int number[COINTYPENUM];//number[i]对应于当前拥有的每种硬币个数
	int tempNum[COINTYPENUM];

	int money=0;//钱数
	int sum=0;//客户拥有的总钱数

	FileProcessor fp;
	vector<float> data;
	fp.getdata(INPUTFILENAME,data);
	question_num = data.size()/7;
	answer = new int[question_num];

	int i=0;
	int j=0;
	int k=0;
	while(i < question_num)
	{
		sum = 0;
		for(j=i*7,k=0; j<data.size()&& k<COINTYPENUM; j++)
		{
			number[k] = (int)data[j];
			k++;
		}
		money = (data[j] +0.001)*100;//+0.001是为了处理精度问题
		for( k=0;k<COINTYPENUM ; k++)
			sum = sum+ value[k]*number[k];
		if(sum%value[0] != 0)
		{
			answer[i] = -1;//表示impossible
			continue;
		}

		for(k=0;k <COINTYPENUM; k++)
			tempNum[k] = number[k];

		answer[i] = -1;

		for(k=money; k<=sum; k+=value[0])
		{
			int give_num=0;//顾客付出的硬币数
			int change_num=0;

			give_num =  getGiveNum( k,number);//得到顾客付出mondy所需的硬币数
			if(give_num != -1)
			{
				int need = k - money;
			    change_num = getChangeNum(need);//得到店家找钱的硬币数
				if(need ==0)
				{
					if(answer[i] == -1 || answer[i]>give_num)
						answer[i] = give_num;
				}
				else if(change_num >0)
				{
					int temp = change_num + give_num;
					if(answer[i]==-1 || answer[i] > temp)
						answer[i] = temp;
				}
			}
		}

		i++;
	}
	vector<string> outputdata;
	for(i=0;i<question_num;i++)
	{
		if(answer[i] != -1)
		{
			cout<<answer[i]<<endl;
			char   string[5];
			sprintf(string, "%d ",   answer[i]);
			outputdata.push_back(string);
		}
		else
		{
			cout<<IMPOSSIBLE<<endl;
			outputdata.push_back(IMPOSSIBLE);
		}
	}
	fp.output_data(OUTPUTFILENAME,outputdata);
	delete [] answer;

	return 0;
}

int getChangeNum(int need)//利用贪心算法得到店家找need钱所需要的最少硬币数
{
	int num = 0;
	for(int coin_index=COINTYPENUM-1; coin_index>=0; coin_index--)
	{
		num+=need/value[coin_index];
		need%=value[coin_index];
	}
	return num;
}

int getGiveNum(int money,int *number)//利用贪心算法得到付出money所需要的最少硬币数
{
	int give_money = money;//顾客付出的钱
	int give_num=0;//顾客付出的硬币数
	int tempNum[COINTYPENUM];

	for(int index=0;index <COINTYPENUM; index++)
		tempNum[index] = number[index];

	for(int coin_index=COINTYPENUM-1; coin_index>=0; coin_index--)
	{
		int n = give_money/value[coin_index];
		if(n <= number[coin_index])
		{
			give_num += n;
			give_money%=value[coin_index];
		}
		else
		{
			give_num += number[coin_index];
			give_money -= number[coin_index] * value[coin_index];
		}
	}
	return give_num;
}
